package demo1;

import java.util.*;

public class Solution {

    public String compressString(String param){
        StringBuffer buf = new StringBuffer();
        char[] s = param.toCharArray();

        int left = 0, right = 0;
        while(left < s.length) {
            while (right + 1 < s.length && s[right + 1] == s[right]) { right++;}
            int len = right - left + 1;
            buf.append(len);
            buf.append(s[left]);
        }
        return buf.toString();
    }


    int[] dp = new int[1010];
    public int knapsack (int V, int n, int[][] vw) {
        for(int i = 0; i < n; i++){
            for(int j = V; j >= vw[i][0]; j--){
                dp[j] = Math.max(dp[j], dp[j - vw[i][0]] + vw[i][1]);
            }
        }
        return dp[V];
    }

    public int[] sortArray(int[] nums) {
        qsort(nums, 0, nums.length - 1);
        return nums;
    }
    public void qsort(int[] nums, int l, int r){
        if(l >= r) { return ;}

        int key = nums[new Random().nextInt(r - l + 1) + l];
        int left = l - 1, right = r + 1, i = l;
        while(i < right){
            if(nums[i] > key){
                swap(nums, --right, i);
            }else if(nums[i] < key){
                swap(nums, ++left, i++);
            }else{
                i++;
            }
        }
        qsort(nums, l, left);
        qsort(nums, right, r);
    }


    public int findKthLargest(int[] nums, int k) {
        return qsort(nums, 0, nums.length - 1, k);
    }
    public int qsort(int[] nums, int l, int r, int k){
        if(l == r) { return nums[l];}
        //1.随机选择一个基准元素
        int key = nums[new Random().nextInt(r - l + 1) + l];
        //2.根据基准元素，使数组分三块
        int left = l - 1, right = r + 1, i = l;
        while(i < right){
            if(nums[i] < key){
                swap(nums, ++left, i++);
            }else if(nums[i] > key){
                swap(nums, --right, i);
            }else{
                i++;
            }
        }
        //3.分类讨论
        int b = right - left - 1, c = r - right + 1;
        if(c >= k){
            return qsort(nums, right, r, k);
        }else if(b + c >= k){
            return key;
        }else{
            return qsort(nums, l, left, k - b - c);
        }
    }
    public void swap(int[] x, int i, int j){
        int t = x[i];
        x[i] = x[j];
        x[j] = t;
    }

    public int[] inventoryManagement(int[] stock, int cnt) {
        int[] ret = new int[cnt];
        if(cnt == 0) { return ret;}

        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for(int i = 0; i < cnt; i++){
            queue.offer(stock[i]);
        }
        for(int i = cnt; i < stock.length; i++){
            if(queue.peek() > stock[i]){
                queue.poll();
                queue.offer(stock[i]);
            }
        }

        for(int i = 0; i < cnt; i++){
            ret[i] = queue.poll();
        }
        return ret;
    }
}
